/**
 * 两数之和
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target的那两个整数，并返回它们的数组下标。
 **/

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

/**
 * Solution 1:暴力解法，两次循环
 **/
class Solution_1 {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(); i++){
            for(int j=i+1; j<nums.size(); j++){
                if(nums[i]+nums[j] == target){
                    return {i,j};
                }
            }
        }
        return {};
    }
};


/**
 * Solution 2:哈希表求解1
*/
class Solution_2{
public:
    vector<int> twoSum(vector<int>& nums, int target){
        // C++11标准不支持hash_map，使用中还是用unordered_map替代
        unordered_map<int, int> hashmap;
        for(int i=0; i<nums.size(); ++i){
            // find:给定主键查找元素
            auto it = hashmap.find(target-nums[i]);
            if(it != hashmap.end()){
                return {it->second, i};
            }
            hashmap[nums[i]] = i;
        }
        // 打印哈希表
        // for(auto& x:hashmap){
        //     cout<<x.first<<":"<<x.second<<endl;
        // }
        return {};
    }
};

int main(){
    Solution_1 s;
    vector<int> nums = {3,2,4};
    int target = 6;
    nums = s.twoSum(nums, target);
    cout<<nums[0]<<','<<nums[1];
}